package sorting

import "gitee.com/guuzaa/sorting/constraints"

func MergeSort[T constraints.Ordered](arr []T) []T {
	mergeSort(arr)

	return arr
}

func mergeSort[T constraints.Ordered](arr []T) {
	if len(arr) > 1 {
		mid := len(arr) >> 1
		mergeSort(arr[:mid])
		mergeSort(arr[mid:])
		merge(arr, mid)
	}
}

func merge[T constraints.Ordered](arr []T, mid int) {
	l, r := 0, mid
	tmp := make([]T, 0, len(arr))

	for l < mid && r < len(arr) {
		if arr[l] <= arr[r] {
			tmp = append(tmp, arr[l])
			l++
		} else {
			tmp = append(tmp, arr[r])
			r++
		}
	}

	for l < mid {
		tmp = append(tmp, arr[l])
		l++
	}

	for r < len(arr) {
		tmp = append(tmp, arr[r])
		r++
	}

	for i := range arr {
		arr[i] = tmp[i]
	}
}

func MergeSort2[T constraints.Ordered](arr []T) []T {
	tmp := make([]T, len(arr))
	var sort func(arr []T, low, high int)

	{
		merge := func(arr []T, low, mid, high int) {
			for i := low; i <= high; i++ {
				tmp[i] = arr[i]
			}

			i, j := low, mid+1
			for p := low; p <= high; p++ {
				switch {
				case i == mid+1:
					arr[p] = tmp[j]
					j++
				case j == high+1:
					arr[p] = tmp[i]
					i++
				case tmp[i] > tmp[j]:
					arr[p] = tmp[j]
					j++
				case tmp[i] <= tmp[j]:
					arr[p] = tmp[i]
					i++
				}
			}
		}

		sort = func(arr []T, low, high int) {
			if low >= high {
				return
			}

			mid := low + (high-low)/2
			sort(arr, low, mid)
			sort(arr, mid+1, high)

			merge(arr, low, mid, high)
		}
	}

	sort(arr, 0, len(arr)-1)

	return arr
}
